//冒泡排序，循环左右交换
function bubbleSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  let flag = false;
  let lastChange = arr.length - 1;
  let k;
  while (!flag) {
    flag = true;
    k = lastChange;
    for (let i = 0; i < k; i++) {
      if (arr[i] > arr[i + 1]) {
        lastChange = i;
        let tem = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tem;
        flag = false;
      }
    }
  }
  return arr;
}

//选择排序，选择最小的放在最前面
function selectSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return;
  for (let i = 0; i < arr.length; i++) {
    minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    let tem = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = tem;
  }
  return arr;
}

//插入排序
function insertSort(arr) {
  if (!Array.isArray(arr) && arr.length <= 1) return arr;
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    j = i;
    while (j - 1 >= 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j = j - 1;
    }
    arr[j] = temp;
  }
  return arr;
}

//希尔排序，有gap的插入排序
function hillSort(array) {
  let length = array.length;

  // 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
  if (!Array.isArray(array) || length <= 1) return;

  // 第一层确定增量的大小，每次增量的大小减半
  for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
    // 对每个分组使用插入排序，相当于将插入排序的1换成了 n
    for (let i = gap; i < length; i++) {
      let temp = array[i];
      let j = i;

      while (j - gap >= 0 && array[j - gap] > temp) {
        array[j] = array[j - gap];
        j -= gap;
      }
      array[j] = temp;
    }
  }

  return array;
}

function mergeSort(array) {
  if (!Array.isArray(array) || array.length <= 0) return;
  if (array.length === 1) return array;
  const leftPart = array.slice(0, parseInt(array.length >> 1));
  const rightPart = array.slice(parseInt(array.length >> 1), array.length);

  return merge(mergeSort(leftPart), mergeSort(rightPart));
}
function merge(left, rigth) {
  const ll = left.length;
  const lr = rigth.length;
  let result = []
  let i=0
  let j=0
  while(i<ll && j<lr){
    if(left[i]<rigth[j]){
      result.push(left[i])
      i++
    }else{
      result.push(rigth[j])
      j++
    }
  }
  while(i<ll){
    result.push(left[i])
    i++
  }
  while(j<lr){
    result.push(rigth[j])
    j++
  }
  return result
}
//快速排序
function quickSort(array, start, end){
  if(!Array.isArray(array) || array.length<=1) return 
  if(array.length===1 || start>=end) return 

  let index=partition(array,start,end)
  quickSort(array,start,index-1)
  quickSort(array,index+1,end)
  
}
function partition(array,start,end){
  const pivot = array[start]
  let low = start
  let high = end
  while(low<high){
    while(high>low && array[high]>pivot){
      high--
    }
    array[low]=array[high]
    while(low<high && array[low]<pivot){
      low++
    }
    array[high]=array[low]
  }
  array[high] = pivot
  return high

}
//堆排序
function swap(array,i,j){
  const temp=array[i]
  array[i]=array[j]
  array[j]=temp
}
function heapSort(array){
  let length = array.length
  if(!Array.isArray(array) || length<=1 ) return
  buildMaxHeap(array)
  for(let i=length-1;i>0;i--){
    swap(array,0,i)
    adjustHeap(array,0,i)
  }
  return arr
}
function buildMaxHeap(array){
  let nodeIndex = parseInt(array.length>>1)-1
  for(let i=nodeIndex;i>=0;i--){
    adjustHeap(array,i,array.length)
  }
}
function adjustHeap(array,top,heapSize){
  let index=top
  while(2*index+2<heapSize){
    let max = index
    let leftLeave = 2*max+1
    let rightLeave = 2*max+2
    if(array[leftLeave]>array[max]){
      max = leftLeave
    }
    if(array[rightLeave]>array[max]){
      max=rightLeave
    }
    if(max!==index){
      swap(array,max,index)
      index=max
    }else{
      break
    }
  }

}
//基数排序
function radixSort(array) {

  let length = array.length;

  // 如果不是数组或者数组长度小于等于1，直接返回，不需要排序 
  if (!Array.isArray(array) || length <= 1) return;
  let bucket = [],
    max = array[0],
    loop;

  // 确定排序数组中的最大值
  for (let i = 1; i < length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }

  // 确定最大值的位数
  loop = (max + '').length;


  // 初始化桶
  for (let i = 0; i < 10; i++) {
    bucket[i] = [];
  }

  for (let i = 0; i < loop; i++) {
    for (let j = 0; j < length; j++) {
      let str = array[j] + '';

      if (str.length >= i + 1) {
        let k = parseInt(str[str.length - 1 - i]); // 获取当前位的值，作为插入的索引
        bucket[k].push(array[j]);
      } else {
        // 处理位数不够的情况，高位默认为 0
        bucket[0].push(array[j]);
      }
    }

    array.splice(0, length); // 清空旧的数组

    // 使用桶重新初始化数组
    for (let i = 0; i < 10; i++) {
      let t = bucket[i].length;

      for (let j = 0; j < t; j++) {
        array.push(bucket[i][j]);
      }

      bucket[i] = [];
    }
  }

  return array;

}